/***
题目链接：栈排序
栈排序。 编写程序，对栈进行排序使最小元素位于栈顶。最多只能使用一个其他的临时栈存放数据，
但不得将元素复制到别的数据结构（如数组）中。该栈支持如下操作：push、pop、peek 和 isEmpty。
当栈为空时，peek 返回 -1。
链接：https://leetcode-cn.com/problems/sort-of-stacks-lcci
***/
class SortedStack {
private:
    stack<int> sta;
    stack<int> temp;
public:
    SortedStack() {

    }
    
    void push(int val) {
    //从栈顶开始弹出，把小于val的元素都先暂存到temp里面
        while((!sta.empty())&&(sta.top()<val)){
            temp.push(sta.top());
            sta.pop();
        }
        sta.push(val);
        while(!temp.empty()){
            sta.push(temp.top());
            temp.pop();
        }
    }
    
    void pop() {
        if (!sta.empty()) sta.pop();
    }
    
    int peek() {
        if (!sta.empty()) 
            return sta.top();
        return -1;
    }
    
    bool isEmpty() {
        return sta.empty();
    }
};

/**
 * Your SortedStack object will be instantiated and called as such:
 * SortedStack* obj = new SortedStack();
 * obj->push(val);
 * obj->pop();
 * int param_3 = obj->peek();
 * bool param_4 = obj->isEmpty();
 */